const MGraph = require('../chapter-12/邻接矩阵')

/**
 * 迪杰斯特拉算法
 * 功能：能够找到最两点之间最短路径的算法
 * 算法的具体步骤：
 *      1：初始化。S只包含源点，即S = {s}，顶点s到自己的距离为0，U包含除s外的其他顶点，源点s到U中顶点i的距离为边上的权，
 *          （若s与i有边<s, i>或顶点i不是s的出边邻接点）
 *      2：从U中选取一个顶点u，它是从源点s到U中距离最小的一个顶点，然后把顶点u加入S中
 *          （该选定的距离就是源点s到顶点u的最短路径长度）
 *      3：以顶点u为新考虑的中间点，修改源点s到U中各顶点j（j属于U）的距离。如从源点s到达顶点j的距离大于源点s到顶点u加上顶点u
 *          到j的距离时，则修改从源点s到顶点j的最短距离值为 s->u + u->j
 *      4: 重复步骤2和步骤3，直到S包含所有顶点，即U为空为止
 */

 /**
  * 寻找两点之间的最短距离（本算法针对邻接矩阵存储方式）
  * @param {*} g 图
  * @param {*} v0 路径的起始点
  * @param {*} ve 路径的终点
  * @param {*} path path用于存放从源点s到顶点i的最短路径上i的前驱点
  * @param {*} dist dist存储从源点s到顶点i的目前最短路径长度
  */
 function dijkstra(g, v0, ve, path, dist) {
    let n = g.vexs.length, s = []
    for (let v = 0; v < n; v++) {
        s[v] = 0 // 数组s用于存储图中顶点是否被访问过（0： 未访问过； 1：被访问过）
        dist[v] = g.edges[v0][v] // 初始化v0到图中各个顶点的距离
        if (dist[v] < 100000) { // 顶点v0到顶点v之间有边时，设置顶点v的前一个顶点为v0
            path[v] = v0
        } else {
            path[v] = -1
        }
    }
    dist[v0] = 0
    s[v0] = 1
    for (let i = 1; i <= n - 1; i++) { // 把剩余的 n - 1 个顶点重复筛选
        let min = 100000, v = -1
        for (let w = 0; w < n; w++) { // 在dist中寻找出w到s顶点最短距离值
            if (!s[w] && dist[w] < min) {
                v = w
                min = dist[w]
            }
        }
        console.log(min)
        if (v == -1) break
        s[v] = 1 // 将顶点v加入s中
        for (let j = 0; j < n; j++) { // 加入新的顶点v到集合s中后，需要更新各个顶点到源点s的距离
            if (!s[j] && ( min + g.edges[v][j] < dist[j])) {
                dist[j] = min + g.edges[v][j]
                path[j] = v
            }
        }
    }

    dotMiniRoute(g, path, s, v0, ve) // 该方法可以获得任何一个顶点到源点的最短路径
 }


 /**
  * 从path数组中寻找从源点s到任何一个顶点i的最短路径
  * 先找到终点，然后在path中定位到终点的位置获取上一个连接点并推入 apath 中，
  * 直到定位到源点结束
  * @param {*} g 图
  * @param {*} path 路径记录表
  * @param {*} s 访问记录表
  * @param {*} v0 路径源点
  * @param {*} v 路径终点
  */
 function dotMiniRoute(g, path, s, v0, v) {
    let i, j, k, apath = [], d, routeStr = ''
    for (i = 0; i < g.vexs.length; i++) { // 找到路径上的终点
        if (s[i] == 1 && i == v) {
            d = 0
            apath[d] = i
            k = path[i]
        } 
    }

    if(k == -1) {
        console.log('无路径')
    } else {
        while(k != v0) { // 从终点进行反推，直到起始点结束
            d++
            apath[d] = k
            k = path[k]
        }
        d++
        apath[d] = v0 // 把源点加入路径中
        for (j = d; j >= 0; j--) {
            routeStr += `->${g.vexs[apath[j]]}`
        }
    }
    
    console.log(routeStr)
 }

/**
 * 主入口
 * @param {*} g 图
 * @param {*} v0 路径起始点
 * @param {*} ve 路径终点
 */
function main(g, v0, ve) {
    const path = [], dist = []
    dijkstra(g, v0, ve, path, dist)
}

 const g = new MGraph(['A', 'B', 'C', 'D'], [{row: 0, col: 1, wei: 10}, {row: 0, col: 3, wei: 20}, {row: 0, col: 2, wei: 80}, {row: 1, col: 2, wei: 40}, {row: 2, col: 3, wei: 20}, {row: 1, col: 3, wei: 9}], '1')
 main(g, 0, 2)